package com.kevinkk.greedy;

import java.util.Arrays;

/**
 * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。
 * 你不知道气球的确切 y 坐标。
 * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
 * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
 */

public class MinimumNumberAfArrowsToBurstBalloons {
    class Solution {
        public int findMinArrowShots(int[][] points) {
            int res = 1;
            // 首先按照 横坐标 从小到大，对所有气球进行排序
            Arrays.sort(points,
                    (p1, p2) -> Integer.compare(p1[0], p2[0]));
            for (int i = 1; i < points.length; i++) {
                // 如果一个气球与前一个气球完全分离（左边大于右边），那么肯定至少需要再多一个箭
                if (points[i][0] > points[i - 1][1]) {
                    res++;
                // 如果一个气球和前一个气球有重合，那么可以将这两个气球完全合并成一个
                // 此时不需要对箭的数量进行处理，因为合并好的气球会交给下一轮做判断
                } else {
                    points[i][1] = Math.min(points[i][1], points[i - 1][1]);
                }
            }
            return res;
        }
    }
}
